FIG. 1 illustrates a generic prior art system for verifying the integrity of computer data 1. File 5 is associated with a digital computer 2, and contains data 1 and a security value S stored in location 7 within file 5. File 5 is accessible to a central processing unit (CPU) 3 of the computer 2. CPU 3 executes program instructions on behalf of the computer 2.
In a first embodiment of the prior art, CPU 3 applies a checksum function against data 1 within file 5, in which all the bytes of file 5, except for the security value S, are added together. This sum is then compared with the security value S. If these two values match, data 1 is deemed not to have been modified, maliciously or otherwise. In this checksum embodiment, the security value S could be stored in a location that is not part of file 5 but is accessible thereto. The problem with this method of file verification is that it is easy to rechecksum file 5 if file 5 has been changed for malicious purposes. For example, a hacker could rather easily maliciously change the contents of data 1, then recompute security value S to correspond with the changed data 1, thus lulling the user of the computer 2 into thinking that the contents of data 1 had not actually changed. This method of data verification can be easily and regrettably reversed engineered to show that the function being used by CPU 3 is a checksum function.
In a second embodiment of the prior art, CPU 3 uses a cyclic redundancy check (CRC) function against the data 1 within file 5. In this embodiment, a CRC of all the bytes in the file 5, not including security value S, is computed by CPU 3 and stored as security value S. Again, S is easy to recompute if the hacker knows that a CRC is being used, and this method of data verification can be relatively easily reverse engineered to show that a CRC is in fact being used.
In a third embodiment of the prior art, CPU 3 uses a cryptographically secure hash function, such as MD5, to create a message digest of the data 1 within file 5, and stores the resulting output hash value in file 5 as security value S. MD5 is described in Schneier, Applied Cryptography, Second Edition (John Wiley & Sons 1996), pp. 436-441, U.S.A. As with the first two prior art embodiments described above, security value S is not used by the hash function when the function is executed. As before, it is easy to recompute the security value S if the hacker knows that MD5 or another hash function is being used, and then to surreptitiously replace the security value S within file 5; and it is easy for the hacker to determine which function is being used.
McNamara, John E., Technical Aspects of Data Communication, 2nd Ed. 1982, Digital Equipment Corporation, U.S.A., pp. 110-122, describes a Cyclic Redundancy Check (CRC) function that is useful in the present invention.
Ore, Oystein, Number Theory and Its History, 1976, Gudrun Ore, U.S.A., pp. 124-129, discuss mathematical problems having two unknowns.